#排排坐分糖果

来源：知乎

#题目

有 n 个小朋友围成一圈；老师给每个小朋友随机发放偶数个糖果，然后进行下面的游戏：

每个小朋友把自己的糖果分一半给左手边的孩子
老师给拥有糖果数量为奇数的小朋友补发一颗糖果使其变成偶数

重复上述步骤，直到所有小朋友的糖果数量都相同。

求老师一共需要补发多少颗糖果？

#分析

这个问题容易出错的地方在于 小朋友把自己的糖果分一半给左手边的孩子 这个行为是并行的。

如果简单的将数组元素的值减小一半加到后一个元素上，就会变成 B 收到 A 给他的糖果后，再分一半给 C。

先加后减、先减后加都是错的：

for i in range(1, N):
    # 接收前面的一半
    array[i] += array[i-1] // 2       # array[i] 改变了

    # 把自己的一半给后面的人
    array[i] -= array[i] // 2         # 根据 array[i] 改变后的值计算，是错误的

for i in range(1, N):
    # 把自己的一半给后面的人
    array[i] -= array[i] // 2

    # 接收前面的一半
    array[i] += array[i-1] // 2       # array[i-1] 在上一轮循环已被改变，根据改变后的值计算，是错误的

这样就导致给多了，需要在接收前面孩子的糖果直接缓存自己的糖果数量。

注意，不能通过直接赋值的方式拷贝可变类型的变量。

#解答

import random

# 随机生成初始状态
N = 10
array = [random.randint(0, 9) * 2 for _ in range(N)]
print('初始状态：', array)

# 补发糖果数
count = 0

# 循环到所有人糖果一样多，即转为集合后长度为 1
while len(set(array)) != 1:
    # 拷贝
    shadow = list(array)

    # 前一个人把一半的糖果给后一个人
    for i in range(1, N):
        array[i] = shadow[i] // 2 + shadow[i-1] // 2

    # 最后一个人把一半糖果给第一个人
    array[0] = shadow[0] // 2 + shadow[N-1] // 2

    print('向左分享：', array)

    # 对奇数补发糖果
    for i in range(N):
        if array[i] & 1:
            array[i] += 1
            count += 1

    print('老师补发：', array)

# 打印结果
print('总共补发：', count)
>>> Establishing WebAssembly Runtime. 
>>> Standby. 
Powered by Shift.

#排排坐 分糖果

#题目

#分析

#解答

#排排坐分糖果